package com.company;


public class Main2 {
    private static void _sort(int a[], int left, int right) {
        int tmp = a[left];
        int l = left;
        int r = right;

        while (l < r) {
            while (l < r && tmp <= a[r]) {
                r--;
            }
            if (l < r) {
                a[l++] = a[r];
            }

            while (l < r && a[l] <= tmp) {
                l++;
            }
            if (l < r) {
                a[r--] = a[l];
            }
        }

        a[l] = tmp;
        if (left < l - 1) {
            _sort(a, left, l - 1);
        }
        if (l + 1 < right) {
            _sort(a, l + 1, right);
        }
    }

    private static void sort(int a[]) {
        int len = a.length;

        _sort(a, 0, len - 1);
    }

    public static void main(String[] args) {
        int N = 20;
        int a[] = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = (int) (Math.random() * N * 10);
        }

        for (int i = 0; i < N; i++) {
            System.out.print(a[i] + "\t");
        }
        System.out.println();

        sort(a);

        for (int i = 0; i < N; i++) {
            System.out.print(a[i] + "\t");
        }
        System.out.println();
    }
}